package src.dp.bag01;

public class no494 {//目标和，装满背包有多少种方法

    /**
     * 1. dp数组下标含义：容量为 j 的背包，装满有 dp[j] 种方法
     * 2. 递推公式：dp[j] += dp[j - nums[i]]
     * 3. 初始化数组：dp[0]=1, 即装满背包为0的方法有一种，放0件物品
     * 4. 遍历顺序：先物品后背包，遍历背包时倒序
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if (Math.abs(target) > sum) return 0; // 此时没有方案
        if ((target + sum) % 2 == 1) return 0; // 此时没有方案

        //只有加法和减法，因此分为两部分 left组合 - right组合 = target
        //eft+right=sum, right=sum-left, 所以left = (target + sum)/2，此时问题就是在集合nums中找出和为left的组合
        //这里的left，就是bagWeight，也就是我们要的背包容量，转变为凑出left组合有几种方法，即装满容量left的包有几种方式
        int bagWeight = (target + sum) / 2;
        int[] dp = new int[bagWeight + 1];
        dp[0] = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=bagWeight; j>=nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagWeight];

    }

}
